# -*- coding: cp1252 -*-
'''Modul zur Sortierung einer unsortierten Liste
Das Modul generiert eine Liste aus Zufallszahlen und
sortiert diese Zahlen in einen neue Liste ein.
Konzept:



args:
   inListe: Liste mit Zufallszahlen die sortiert werden sollen
   outfile: Name der Ausgabedatei

'''
import random
import time
###############################Liste generieren#######################################################################
random.seed(5)
L = random.sample(xrange(1000), 1000)                                                                                   #Unsortierte Liste generieren
##############################Variablen###############################################################################
startTime = time.time()
Lneu=[L[0]]                                                                                                             #Ziel-Liste erstellen mit Inhalt= erstes Element aus Unsortierter Liste
##############################Fall für i=1 lösen#######################################################################
if L[1]>Lneu[0]:                                                                                                        #Da Fall i=0 und i=1 nicht in Schleife so beruecksichtigt werden können, wird hier 2. Listenelement einsortiert
	Lneu.append(L[1])                                                                                               #wenn 2.element groeßer als 1. dann dahinter einsortieren...
else:
	Lneu.insert(0, L[1])                                                                                            #...sonst an erster (=0.)Stelle
########################################################################################################################
##############################Jede Zahl aus Liste einsortieren############################################################
########################################################################################################################
for i in range(2,len(L)):                                                                                               #für alle anderen Listenelemente
        Zahl=L[i]                                                                                                       #"Zahl" ist das i-te Listenelement
        mitte=len(Lneu)/2                                                                                               #Mitte ist Halbe Listenlänge
        if Zahl>Lneu[len(Lneu)-1]:                                                                                      #WennZahl größer als letztes Element aus neuer Liste dann einfach anhängen
                Lneu.append(Zahl)
        else:
                if Zahl<Lneu[0]:                                                                                        #Wenn zahl kleiner als 0.Element der Liste dann vorne dranhängen
                        Lneu.insert(0,Zahl)
                else:
                        MinMitte=0                                                                                      #Ansonsten ist die Zahl irgendwo zwischen 0...
                        MaxMitte=len(Lneu)                                                                              #...un der maximalen Länge der neuen liste einzusortieren:
############################# So lange Liste halbieren (Min/MaxMitte eingränzen) bis sich Zahl dort einordnen lässt #####################################
                        while (Zahl<Lneu[mitte] and Zahl < Lneu[mitte-1]) or (Zahl>Lneu[mitte] and Zahl>Lneu[mitte+1]): #bis die Zahl nicht zwischen Zahl in Mitte und Zahl davor/danach past
                                if Zahl > Lneu[mitte] and Zahl>Lneu[mitte+1]:                                           #schaue ob Zahl größer als Mitte. Wenn Ja dann...
                                        MinMitte=mitte                                                                  #setze die MinMitte = aktueller Mitte weil die Mitte nicht kleiner werden kann
                                        mitte=mitte+len(range(mitte,MaxMitte))/2                                        #grenze Suchbereich auf bereich zwischen aktueller Mitte un maximaler Mitte ein
                                else:                                                                                   #Schaue ob Zahl kleiner als aktuelle Mitte. Wenn ja dann:
                                        MaxMitte=mitte                                                                  #setze die MaxMitte auf aktuelle Mitte weil die Mitte nicht größer werden kann 
                                        mitte=len(range(MinMitte,mitte))/2                                              #grenze Suchbereich auf bereich zwischen MinMitte und aktueller Mitte ein
##################################### Zahl einordnen ###########################################################################
                        if Zahl>Lneu[mitte]:                                                                            #wenn Zahl größer als Zahl der Mitte dann dahinter einsortieren...
                                Lneu.insert(mitte+1,Zahl)
                        if Zahl<Lneu[mitte]:                                                                            #...ansonsten davor
                                Lneu.insert(mitte,Zahl)  
########################################################################################################################
##################################Ergebnis ausgeben#######################################################################
########################################################################################################################
endTime = time.time()
elapsed = endTime - startTime
print "Liste unsortiert:", L
print "Liste sortiert:", Lneu
print "Dauer",elapsed,"Seconds"
